package com.example.websocket.sort;

import java.util.Arrays;

/**
 * 快速排序，设定一个基准值，分别从最左边和最右边分别寻找第一个大于基准值和小于基准值的值，
 * 并进行交换，以此类推，当寻找到同一个位置后退出循环
 * ------------------------------------------------------------------------------
 * 快速排序平均时间复杂度也为O(nlogn)级。
 */
public class QuickSort {

    public int partition(int[] nums, int begin, int end) {
//        for (int i = begin; i < end; i++) {
//            if (nums[i] > nums[end]) {
//                int temp = nums[i];
//                nums[i] = nums[end];
//                nums[end] = temp;
//            }
//        }
//        return end;
        int left = nums[begin];
        int i = begin;
        int j = end;
        while (i < j) {
            while (i < j && nums[j] >= left) {
                j--;
            }
            while (j > i && nums[i] <= left) {
                i++;
            }
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
        nums[begin] = nums[i];
        nums[i] = left;
        return i;
    }

    public void quickSort(int[] nums, int begin, int end) {
        if (end <= begin)
            return;
        int pivot = partition(nums, begin, end);
        quickSort(nums, begin, pivot - 1);
        quickSort(nums, pivot + 1, end);
    }

    public static void main(String[] args) {
//        int[] array = new int[]{3, 44, 38, 27, 38, 2, 19, 1, 39, 20, 5, 50, 48};
//        int[] array = new int[]{3, 44, 38, 27, 38, 50, 19, 1, 39, 20, 5, 2, 48, 100, 203, 30, 40, 10, 60, 210, 103, 402,106, 70, 33};
        int[] array = new int[]{9,8,7,6,5,4,3,2,1};
        /**
         * end12 c12
         * 3, 44, 38, 27, 1, 19, 2, 39, 20, 5, 50, 48
         * end11 c11
         * 3, 44, 38, 27, 2, 19, 1, 39, 20, 5, 48, 50
         * end10 c
         * 3, 5, 38, 27, 2, 19, 1, 39, 20, 44, 48, 50
         * 3, 5, 20, 27, 2, 19, 1, 38, 39, 44, 48, 50
         */
        QuickSort q = new QuickSort();
        long startTime = System.nanoTime();;
        q.quickSort(array, 0, array.length - 1);
        long endTime = System.nanoTime();;
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(array));
    }
}
